/*
 * @lc app=leetcode.cn id=2049 lang=cpp
 *
 * [2049] 统计最高分的节点数目
 */

// @lc code=start
class Solution
{
public:
    int n;

    long long dfs(int node, int &ans, long long &maxScore, vector<vector<int>> &children)
    {
        long long score = 1, sum = 1;
        for (auto child : children[node])
        {
            int childNum = dfs(child, ans, maxScore, children);
            score *= childNum;
            sum += childNum;
        }
        // 如果不是根节点，可以计算非左右子树的最大分数
        if (node != 0)
        {
            score *= n - sum;
        }
        // 更新最大分数
        if (score == maxScore)
        {
            ans++;
        }
        else if (score > maxScore)
        {
            maxScore = score;
            ans = 1;
        }
        return sum;
    }

    int countHighestScoreNodes(vector<int> &parents)
    {
        n = parents.size();
        vector<vector<int>> children(n, vector<int>());
        for (int i = 0; i < n; i++)
        {
            int idx = parents[i];
            if (idx == -1)
            {
                continue;
            }
            children[idx].push_back(i);
        }

        int ans = 0;
        long long maxScore = 0;
        dfs(0, ans, maxScore, children);
        return ans;
    }
};
// @lc code=end
